\documentclass{beamer}
\usepackage[utf8]{inputenc}
\beamertemplateshadingbackground{red!10}{blue!10}
%\usepackage{fancybox}
\usepackage{epsfig}
\usepackage{verbatim}
\usepackage{url}
%\usepackage{graphics}
%\usepackage{xcolor}
\usepackage{fancybox}
\usepackage{moreverb}
%\usepackage[all]{xy}
\usepackage{listings}
\usepackage{filecontents}
\usepackage{graphicx}

\lstset{
  language=Lisp,
  basicstyle=\scriptsize\ttfamily,
  keywordstyle={},
  commentstyle={},
  stringstyle={}}

\def\inputfig#1{\input #1}
\def\inputeps#1{\includegraphics{#1}}
\def\inputtex#1{\input #1}

\inputtex{logos.tex}

%\definecolor{ORANGE}{named}{Orange}

\definecolor{GREEN}{rgb}{0,0.8,0}
\definecolor{YELLOW}{rgb}{1,1,0}
\definecolor{ORANGE}{rgb}{1,0.647,0}
\definecolor{PURPLE}{rgb}{0.627,0.126,0.941}
\definecolor{PURPLE}{named}{purple}
\definecolor{PINK}{rgb}{1,0.412,0.706}
\definecolor{WHEAT}{rgb}{1,0.8,0.6}
\definecolor{BLUE}{rgb}{0,0,1}
\definecolor{GRAY}{named}{gray}
\definecolor{CYAN}{named}{cyan}

\newcommand{\orchid}[1]{\textcolor{Orchid}{#1}}
\newcommand{\defun}[1]{\orchid{#1}}

\newcommand{\BROWN}[1]{\textcolor{BROWN}{#1}}
\newcommand{\RED}[1]{\textcolor{red}{#1}}
\newcommand{\YELLOW}[1]{\textcolor{YELLOW}{#1}}
\newcommand{\PINK}[1]{\textcolor{PINK}{#1}}
\newcommand{\WHEAT}[1]{\textcolor{wheat}{#1}}
\newcommand{\GREEN}[1]{\textcolor{GREEN}{#1}}
\newcommand{\PURPLE}[1]{\textcolor{PURPLE}{#1}}
\newcommand{\BLACK}[1]{\textcolor{black}{#1}}
\newcommand{\WHITE}[1]{\textcolor{WHITE}{#1}}
\newcommand{\MAGENTA}[1]{\textcolor{MAGENTA}{#1}}
\newcommand{\ORANGE}[1]{\textcolor{ORANGE}{#1}}
\newcommand{\BLUE}[1]{\textcolor{BLUE}{#1}}
\newcommand{\GRAY}[1]{\textcolor{gray}{#1}}
\newcommand{\CYAN}[1]{\textcolor{cyan }{#1}}

\newcommand{\reference}[2]{\textcolor{PINK}{[#1~#2]}}
%\newcommand{\vect}[1]{\stackrel{\rightarrow}{#1}}

% Use some nice templates
\beamertemplatetransparentcovereddynamic

\newcommand{\A}{{\mathbb A}}
\newcommand{\degr}{\mathrm{deg}}

\title{Representing method combinations}

\author{Robert Strandh}
\institute{
LaBRI, University of Bordeaux
}
\date{April, 2020}

%\inputtex{macros.tex}


\begin{document}
\frame{
\resizebox{3cm}{!}{\includegraphics{Logobx.pdf}}
\hfill
\resizebox{1.5cm}{!}{\includegraphics{labri-logo.pdf}}
\titlepage
\vfill
\small{European Lisp Symposium, Zürich, Switzerland \hfill ELS2020}
}

\setbeamertemplate{footline}{
\vspace{-1em}
\hspace*{1ex}{~} \GRAY{\insertframenumber/\inserttotalframenumber}
}

\frame{
\frametitle{Context: The \sicl{} project}

https://github.com/robert-strandh/SICL

Several objectives:

\begin{itemize}
\item Create high-quality \emph{modules} for implementors of
  \commonlisp{} systems.
\item Improve existing techniques with respect to algorithms and data
  structures where possible.
\item Improve readability and maintainability of code.
\item Improve documentation.
\item Ultimately, create a new implementation based on these modules.
\end{itemize}
}

\frame{
\frametitle{Generic function}
A feature of object-oriented programming languages.
\vskip 0.25cm
Can be thought of as a collection of \emph{methods} sharing the same
name.
\vskip 0.25cm
In traditional languages, a generic function is not a first-class object.
\vskip 0.25cm
In \commonlisp{} a generic function is an instance of a subclass of
\texttt{function}, so it is a first-class object.
}

\frame{
\frametitle{Generic-function invocation}
In traditional languages: \texttt{<arg1>.gf(<arg2>, ...)}
\vskip 0.25cm
In \commonlisp{} \texttt{(gf <arg1> <arg2> ...)}
\vskip 0.25cm
Because of subclassing, an invocation may result in several methods
being \emph{applicable}.
}

\frame{
\frametitle{Traditional generic-function invocation}
In traditional languages, only the most specific applicable method is
invoked.
\vskip 0.25cm
Invoking less specific methods requires an explicit call, such as
\texttt{super(...)}.
\vskip 0.25cm
Explicit code is required to combine the results of the different
applicable methods being called.
}

\frame{
\frametitle{Generic-function invocation in \commonlisp{}}
The applicable methods are \emph{combined} in some way.
\vskip 0.25cm
The combination is expressed as a lambda expression called the
\emph{effective method}.
\vskip 0.25cm
The effective method contains calls to the individual methods.
\vskip 0.25cm
The compiler is called in order to turn the effective method into an
\emph{effective method function}.
\vskip 0.25cm
When applied to the arguments of the invocation of the generic
function, the effective method function calls the methods in the right
order.
}

\frame{
\frametitle{\texttt{compute-effective-method}}
This generic function has three parameters:
\begin{enumerate}
\item A generic-function metaobject
\item A method-combination metaobject
\item A list of method metaobjects
\end{enumerate}
\vskip 0.25cm
A call to this generic function returns an an effective method.
}


\frame{
\frametitle{Role of the method-combination metaobject}
In \texttt{compute-effective-method}, the method-combination
metaobject designates a \emph{method-combination procedure}.
\vskip 0.25cm
This procedure can be implemented in different ways:
\begin{itemize}
\item As a method on \texttt{compute-effective-method}, specialized to
  some method-combination class.
\item As a function stored in the method-combination object.
\item Any other way that will accomplish the task.
\end{itemize}
}

\frame{
\frametitle{Method combinations in the \commonlisp{} standard}
A system class \texttt{method-combination} is defined.
\vskip 0.25cm
Method-combination metaobjects must be \emph{indirect instances} of this
class.
\vskip 0.25cm
A method-combination metaobject contains information about its
\emph{type} and the \emph{arguments} used with that type.
}

\frame[containsverbatim]{
\frametitle{Example use of method combinations}
\begin{verbatim}
(defgeneric foo (x)
  (:method-combination and :most-specific-last))
\end{verbatim}
\vskip 0.25cm
Here, \texttt{and} is the name of a method-combination \emph{type} and
\texttt{:most-specific-last} is an \emph{argument} that this
particular type accepts.
\vskip 0.25cm
The applicable methods are combined with the \texttt{and} standard
operator, and the arguments to the operator are the return values of
the invocations of the applicable methods in the order of the least
specific to most specific.
}

\frame{
\frametitle{\texttt{define-method-combination}}
This operator defines a method-combination \emph{type}
\vskip 0.25cm
It has two \emph{versions}: the \emph{short} version and the
\emph{long} version.
}

\frame{
\frametitle{\texttt{define-method-combination} (short version)}
\texttt{(define-method-combination} \emph{name} \emph{options}\texttt{)}
\vskip 0.25cm
Options are unimportant for this presentation.
\vskip 0.25cm
The short version defines a method-combination type that accepts an
\emph{optional argument} that can be \texttt{:most-specific-first} or
\texttt{:most-specific-last}.
\vskip 0.25cm
If no argument is given, it defaults to \texttt{:most-specific-first}.
}

\frame[containsverbatim]{
\frametitle{\texttt{define-method-combination} (long version)}
\texttt{(define-method-combination} \emph{name} \emph{lambda-list}
... \emph{body} \texttt{)}
\vskip 0.25cm
The ... represent information that is not important to this
presentation.
\vskip 0.25cm
The \emph{lambda-list} is an ordinary lambda list that specifies what
\emph{arguments} can be given after \texttt{:method-combination}.
}

\frame{
\frametitle{Scenarios}
\begin{enumerate}
\item The user defines a method-combination type using
  \texttt{define-method-combination}, then uses that type in a
  \texttt{defgeneric} form, but makes a mistake in the arguments.
\item The user defines a method-combination type using the long
  version of \texttt{define-method-combination}, but makes a mistake
  in the lambda list.  Then uses \texttt{defgeneric} with the intended
  arguments.
\item The user defines a method-combination type using the long
  version of \texttt{define-method-combination}, then uses
  \texttt{defgeneric} with acceptable arguments.  Later, the user
  modifies the lambda list and redefines the method-combination type.
\end{enumerate}

}

%% \frame{
%% \frametitle{\texttt{find-method-combination}}
%% This generic function is called with the name of a method-combination
%% type and the arguments supplied in the \texttt{defgeneric} form.
%% \vskip 0.25cm
%% It returns a method-combination metaobject.
%% }

\frame{
\frametitle{Previous work}
We investigated several FLOSS implementations:
\begin{itemize}
\item Portable Common Loops (PCL).  A mostly portable library used for
  adding CLOS to a pre-ANSI \commonlisp{} implementation.
\item Steel Bank Common Lisp (SBCL)
\item Clozure Common Lisp (CCL)
\item Embedded Common Lisp (ECL)
\item Clasp
\end{itemize}
\vskip 0.25cm
Many of them fail several scenarios.
\vskip 0.25cm
All of them sometimes fail to verify the validity of method-combination
arguments early.  Instead, the arguments are sometimes verified when
\texttt{compute-effective-method} is called, resulting in cryptic
error messages.
\vskip 0.25cm
Details in the paper.
}

\frame{
\frametitle{Our technique}
\vskip 0.25cm
\begin{figure}
\begin{center}
\inputfig{fig-method-combinations.pdf_t}
\end{center}
\end{figure}
}

\frame{
\frametitle{Our technique}
In this presentation, we cover only our technique for reporting
incorrect method-combination arguments early.
\vskip 0.25cm
Refer to the paper for the way we handle the other scenarios.
}

\frame[containsverbatim]{
\frametitle{Our technique}
Recall the long version of \texttt{define-method-combination}:
\texttt{(define-method-combination} \emph{name} \emph{lambda-list}
... \emph{body} \texttt{)}
\vskip 0.25cm
The \emph{lambda-list} is an ordinary lambda list that specifies what
\emph{arguments} can be given after \texttt{:method-combination}.
\vskip 0.25cm
We translate the short version to the long version.
\vskip 0.25cm
We analyze the \emph{lambda-list} of the long version and extract all the
parameters (say v1, ..., vn) that can be used in the \emph{body}.
}

\frame{
\frametitle{Our technique}
We construct a lambda expression as follows:
\vskip 0.25cm
\texttt{(lambda (...) (list v1 ... vn))}
\vskip 0.25cm
where (...) is the original lambda list.
\vskip 0.25cm
We compile the lambda expression to obtain a function.
\vskip 0.25cm
When this function is applied to the method-combination arguments, it
returns a list of objects that can be used to identify a particular
method-combination metaobject of a given type.
\vskip 0.25cm
This list is used for recycling existing method-combination metaobjects.
}

\frame[containsverbatim]{
\frametitle{Our technique}
In our \texttt{define-method-combination} forms, we include
\texttt{\&aux} parameters with expressions that verify the arguments.
\vskip 0.25cm
Example of long version for method-combination type \texttt{and}:
\vskip 0.25cm
\begin{verbatim}
(define-method-combination and
    (&optional (order :most-specific-first)
     &aux (ignore (unless (member order
                                  '(:most-specific-first
                                    :most-specific-last))
                    (error ...))))
 ...)
\end{verbatim}

}

\frame{
\frametitle{Our technique}
When our constructed function is applied to some incorrect
method-combination arguments:
\begin{itemize}
\item It may fail because the arguments are incompatible with the
  parameters of the lambda list.
\item It may fail because one or more \texttt{\&aux} initialization
  forms call \texttt{error}.
\end{itemize}
\vskip 0.25cm
In both cases, we handle the error and report incorrect arguments.
}


\frame{
\frametitle{Future work}
The technique described here has been only partially incorporated into
SICL.  We are working on finishing this incorporation.
\vskip 0.25cm
Our technique could benefit from some \emph{weak} data structure to
avoid memory leaks due to generic-function metaobjects being stored in
our data structure.  SICL does not yet have any such data structure.
We plan to add it.
\vskip 0.25cm
\vskip 0.25cm
\vskip 0.25cm

}

\frame{
  \frametitle{Acknowledgments}

We would like to thank Yan Gajdoš and Cyrus Harmon for providing
valuable feedback on early versions of this paper.
}

\frame{
\frametitle{Thank you}
}

%% \frame{\tableofcontents}
%% \bibliography{references}
%% \bibliographystyle{alpha}

\end{document}
